package com.LeeCode;

import java.util.HashMap;

/**
 * 从中序与后序遍历序列构造二叉树
 */

public class Code106 {
    public static void main(String[] args) {
        int[] inorder = {9, 3, 15, 20, 7}, postorder = {9, 15, 7, 20, 3};
        TreeNode root = new Code106().buildTree(inorder, postorder);
    }

    HashMap<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        int n = postorder.length;
        return build(postorder, 0, n - 1, 0);
    }

    private TreeNode build(int[] postorder, int postLeft, int postRight, int inLeft) {
        if (postLeft > postRight) return null;
        TreeNode root = new TreeNode(postorder[postRight]);
        int rootIndex = map.get(postorder[postRight]);
        int numLeft = rootIndex - inLeft;
        root.left = build(postorder, postLeft, postLeft + numLeft - 1, inLeft);
        root.right = build(postorder, postLeft + numLeft, postRight - 1, rootIndex + 1);
        return root;
    }
}
